package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 * */
public class Search {
    public static void main(String[] args) {
        Search obj = new Search();
        int search = obj.search(new int[]{5, 7, 7, 8, 8, 10}, 8);
        System.out.println(search);
    }

    /**
     *  方法1：二分查找 + 扩散法
     *  思路：
     *      因为是有序的数组，所以可以用二分法来找到target，然后从这个target向两边扩散
     *      1.先通过二分法，找到某一个与target相同的元素的下标。
     *      2.再通过这个下标向两边扩散，直到所有相同元素遍历完成，结束移动左右下标
     *      3，元素个数就是这个下标的范围长度。
     * */
    public int search(int[] nums, int target) {
        int left =0;
        int right = nums.length -1;
        int center = -1;
        //先定位某一个target的位置
        while(left <= right){
            int mid = (right + left )/2;
            if(nums[mid] == target){
                center =mid;
                break;
            }else if(nums[mid] > target){
                right = mid -1;
            }else{
                left = mid +1;
            }
        }
        if(center == -1 ){
            return 0;
        }
        //两边扩散，统计个数
        //向右扩散
        for (int i = center; i < nums.length; i++) {
            if(nums[i] != target){
                right = i -1;
                break;
            }
        }
        //向左扩散
        for (int j = center;j >=0; j--) {
            if(nums[j] != target){
                left = j + 1;
                break;
            }
        }
        return right - left + 1;
    }
}
